/*
https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/fen-ge-hui-wen-chuan-ii-by-leetcode-solu-norx/
 */
import java.util.Arrays;

public class Solution132 {
    public int minCut(String s) {
        int[] f=new int[s.length()+1];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        boolean[][] g=new boolean[s.length()][s.length()];
        for (int i=0;i<s.length();i++){
            Arrays.fill(g[i],true);
        }
        for (int i=s.length()-1;i>=0;i--){
            for (int j=i+1;j<s.length();j++){
                g[i][j]=s.charAt(i)==s.charAt(j)&&g[i+1][j-1];
            }
        }
        for (int i=1;i<=s.length();i++){
            for (int j=0;j<i;j++){
                if (g[j][i-1]){
                    f[i]=Math.min(f[i],f[j]+1);
                }
            }
        }
        return f[s.length()]-1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution132().minCut("aab"));
    }
}
